//
//  9.跳台阶扩展问题.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/17.
//

import Foundation
/*
 题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 思路：f(n) = f(n-1) + f(n-2) + ... + f(0)（数学归纳法）
 */
func offer_9() {
    print(Solution().jumpFloor(10))
}

fileprivate class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型
     * @return int整型
     */
    func jumpFloor(_ n: Int) -> Int {
        // write code here
        /*
         f(n) = f(n-1) + f(n-2) + ... + f(0)
         f(n-1) = f(n-2) + f(n-3) + ... + f(0)
         f(n) = 2*f(n-1)
         */
        return 2 << (n-2)
    }
}
